package codetop.dp;

public class Code064 {
    public int minPathSum(int[][] grid) {
        int [][]dp=new int[grid.length][grid[0].length];
        int count=0;
        for (int i = 0; i < grid.length; i++) {
                count+=grid[i][0];
                dp[i][0]=count;
        }
        for (int i = 0; i < grid[0].length; i++) {
            count+=grid[0][i];
            dp[0][i]=count;
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j <grid[0].length ; j++) {
                dp[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}
